// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。逃逸分析。

package escape

import (
	"fmt"

	"cmd/compile/internal/base"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/logopt"
	"cmd/compile/internal/typecheck"
	"cmd/compile/internal/types"
)

// 
// 在这里，我们分析函数，以确定哪些Go变量
// （包括隐式分配，例如对“new”或“make”的调用，
// 复合文本等）可以在堆栈上分配。我们必须确保的两个关键不变量是：（1）指向堆栈对象的指针不能存储在堆中，和（2）指向堆栈对象
// 的指针不能超过该对象的寿命（例如，因为声明函数
// 返回并销毁了对象的堆栈帧，或者其空间是
// 在逻辑上不同的变量的循环迭代中重复使用）。
// 
// 我们通过对AST的静态数据流分析来实现这一点。首先，我们构造一个有向加权图，其中顶点
// （称为“位置”）表示由语句
// 和表达式分配的变量，边表示变量之间的赋值
// （权重表示寻址/解引用计数）。
// 
// 接下来我们在图中寻找可能违反上述不变量的赋值路径。如果变量v的地址是
// 存储在堆中或可能比它更长寿的其他地方，那么v是
// 标记为需要堆分配。
// 
// 为了支持过程间分析，我们还记录了从
// 每个函数的参数到堆及其结果的数据流
// 参数。这些信息被总结为“参数标签”，
// 用于静态调用站点，以改进
// 函数参数的转义分析。

// 构建位置图。
// 
// 每个分配语句（例如，变量声明）或
// 表达式（例如，“new”或“make”）首先映射到唯一的
// “location”
// 
// 我们还将每个Go分配建模为
// 位置之间的有向边。解引用操作的数量减去
// 寻址操作的数量被记录为边的权重（称为
// “解引用”）。例如：
// 
// p=&q
// p=q
// p=*q
// p=**q
// 
// p=
// 
// 请注意，&运算符只能应用于可寻址的
// 表达式，表达式&x本身是不可寻址的，因此
// derefs不能低于-1。
// 
// 每一个Go语言结构都被降低到这个表示中，
// 通常对流、路径或上下文不敏感；和
// 不区分复合变量中的元素。对于
// 示例：
// 
// var x struct{f，g*int}
// var u[]*int 
// 
// x.f=u[0]
// 
// 被简单地建模为
// 
// u[2]等。然而，我们确实记录了索引切片时涉及的隐式解引用
// 。

// 一个批处理包含一个转义分析状态，该状态在整个
// 一次分析一批函数时共享。
type batch struct {
	allLocs  []*location
	closures []closure

	heapLoc  location
	blankLoc location
}

// 一个闭包包含一个闭包表达式及其溢出孔（即，
// 其中表示存储到其闭包记录中的孔）。
type closure struct {
	k   hole
	clo *ir.ClosureExpr
}

// 转义将特定于正在分析的单个函数的状态保存在批处理中。
type escape struct {
	*batch

	curfn *ir.Func // 正在分析的函数

	labels map[*types.Sym]labelState // 已知标签

	// loopDepth统计
	// curfn中的当前循环嵌套深度。它在每个“for”循环中递增，在每个
	// 标签上递增，并带有相应的向后“goto”（即
	// 非结构化循环）。
	loopDepth int
}

func Funcs(all []ir.Node) {
	ir.VisitFuncsBottomUp(all, Batch)
}

// 批对
// 函数的最小批执行转义分析。
func Batch(fns []*ir.Func, recursive bool) {
	for _, fn := range fns {
		if fn.Op() != ir.ODCLFUNC {
			base.Fatalf("unexpected node: %v", fn)
		}
	}

	var b batch
	b.heapLoc.escapes = true

	// 从语法树构造数据流图。
	for _, fn := range fns {
		if base.Flag.W > 1 {
			s := fmt.Sprintf("\nbefore escape %v", fn)
			ir.Dump(s, fn)
		}
		b.initFunc(fn)
	}
	for _, fn := range fns {
		if !fn.IsHiddenClosure() {
			b.walkFunc(fn)
		}
	}

	// 我们已经遍历了函数体，所以我们到处都可以看到一个
	// 变量可能被重新赋值或被取了地址。现在我们
	// 可以决定闭包是否应该通过值或引用捕获其自由变量
	// 。
	for _, closure := range b.closures {
		b.flowClosure(closure.k, closure.clo)
	}
	b.closures = nil

	for _, loc := range b.allLocs {
		if why := HeapAllocReason(loc.n); why != "" {
			b.flow(b.heapHole().addr(loc.n, why), loc)
		}
	}

	b.walkAll()
	b.finish(fns)
}

func (b *batch) with(fn *ir.Func) *escape {
	return &escape{
		batch:     b,
		curfn:     fn,
		loopDepth: 1,
	}
}

func (b *batch) initFunc(fn *ir.Func) {
	e := b.with(fn)
	if fn.Esc() != escFuncUnknown {
		base.Fatalf("unexpected node: %v", fn)
	}
	fn.SetEsc(escFuncPlanned)
	if base.Flag.LowerM > 3 {
		ir.Dump("escAnalyze", fn)
	}

	// 为局部变量分配位置。
	for _, n := range fn.Dcl {
		e.newLoc(n, false)
	}

	// 也用于隐藏参数（例如，
	// 方法值包装的“.this”参数）。
	if fn.OClosure == nil {
		for _, n := range fn.ClosureVars {
			e.newLoc(n.Canonical(), false)
		}
	}

	// 初始化结果参数的结果索引。
	for i, f := range fn.Type().Results().FieldSlice() {
		e.oldLoc(f.Nname.(*ir.Name)).resultIndex = 1 + i
	}
}

func (b *batch) walkFunc(fn *ir.Func) {
	e := b.with(fn)
	fn.SetEsc(escFuncStarted)

	// 识别标记非结构化循环头部的标签。
	ir.Visit(fn, func(n ir.Node) {
		switch n.Op() {
		case ir.OLABEL:
			n := n.(*ir.LabelStmt)
			if e.labels == nil {
				e.labels = make(map[*types.Sym]labelState)
			}
			e.labels[n.Label] = nonlooping

		case ir.OGOTO:
			// 如果我们在goto之前访问了标签，
			// 那么这是一个循环标签。
			n := n.(*ir.BranchStmt)
			if e.labels[n.Label] == nonlooping {
				e.labels[n.Label] = looping
			}
		}
	})

	e.block(fn.Body)

	if len(e.labels) != 0 {
		base.FatalfAt(fn.Pos(), "leftover labels after walkFunc")
	}
}

func (b *batch) flowClosure(k hole, clo *ir.ClosureExpr) {
	for _, cv := range clo.Func.ClosureVars {
		n := cv.Canonical()
		loc := b.oldLoc(cv)
		if !loc.captured {
			base.FatalfAt(cv.Pos(), "closure variable never captured: %v", cv)
		}

		// 按值捕获从不重新分配的<=128字节的变量。
		n.SetByval(!loc.addrtaken && !loc.reassigned && n.Type().Size() <= 128)
		if !n.Byval() {
			n.SetAddrtaken(true)
			if n.Sym().Name == typecheck.LocalDictName {
				base.FatalfAt(n.Pos(), "dictionary variable not captured by value")
			}
		}

		if base.Flag.LowerM > 1 {
			how := "ref"
			if n.Byval() {
				how = "value"
			}
			base.WarnfAt(n.Pos(), "%v capturing by %s: %v (addr=%v assign=%v width=%d)", n.Curfn, how, n, loc.addrtaken, loc.reassigned, n.Type().Size())
		}

		// 将捕获的变量流到闭包。
		k := k
		if !cv.Byval() {
			k = k.addr(cv, "reference")
		}
		b.flow(k.note(cv, "captured by a closure"), loc)
	}
}

func (b *batch) finish(fns []*ir.Func) {
	// 记录包裹导出数据的参数标签。
	for _, fn := range fns {
		fn.SetEsc(escFuncTagged)

		narg := 0
		for _, fs := range &types.RecvsParams {
			for _, f := range fs(fn.Type()).Fields().Slice() {
				narg++
				f.Note = b.paramTag(fn, narg, f)
			}
		}
	}

	for _, loc := range b.allLocs {
		n := loc.n
		if n == nil {
			continue
		}
		if n.Op() == ir.ONAME {
			n := n.(*ir.Name)
			n.Opt = nil
		}

		// 根据逃逸分析结果更新n.Esc。

		// 至少目前，忽略go/defer包装器的转义诊断。
		// 历史上，我们没有打印它们，测试用例也不期望它们。
		// TODO（mdempsky）：更新测试以预期这一点。
		goDeferWrapper := n.Op() == ir.OCLOSURE && n.(*ir.ClosureExpr).Func.Wrapper()

		if n.Op() == ir.OCONVIDATA && n.(*ir.ConvExpr).NonEscaping {
			// 已知接口数据字的分配不会转义。
			// 见第50182期。
			// （但我们仍然需要处理该分配，因为
			// 内的指针可能会逃逸数据字。）
			loc.escapes = false
		}

		if loc.escapes {
			if n.Op() == ir.ONAME {
				if base.Flag.CompilingRuntime {
					base.ErrorfAt(n.Pos(), "%v escapes to heap, not allowed in runtime", n)
				}
				if base.Flag.LowerM != 0 {
					base.WarnfAt(n.Pos(), "moved to heap: %v", n)
				}
			} else {
				if base.Flag.LowerM != 0 && !goDeferWrapper {
					base.WarnfAt(n.Pos(), "%v escapes to heap", n)
				}
				if logopt.Enabled() {
					var e_curfn *ir.Func // TODO（mdempsky）：修复。
					logopt.LogOpt(n.Pos(), "escape", "escape", ir.FuncName(e_curfn))
				}
			}
			n.SetEsc(ir.EscHeap)
		} else {
			if base.Flag.LowerM != 0 && n.Op() != ir.ONAME && !goDeferWrapper {
				base.WarnfAt(n.Pos(), "%v does not escape", n)
			}
			n.SetEsc(ir.EscNone)
			if loc.transient {
				switch n.Op() {
				case ir.OCLOSURE:
					n := n.(*ir.ClosureExpr)
					n.SetTransient(true)
				case ir.OMETHVALUE:
					n := n.(*ir.SelectorExpr)
					n.SetTransient(true)
				case ir.OSLICELIT:
					n := n.(*ir.CompLitExpr)
					n.SetTransient(true)
				}
			}
		}
	}
}

// inMutualBatch报告函数fn是否在正在分析的相互递归函数批中。如果这是真的，
// fn尚未分析，因此其参数和结果
// 应直接并入流图中，而不是依赖其转义分析标签
// 中。
func (e *escape) inMutualBatch(fn *ir.Name) bool {
	if fn.Defn != nil && fn.Defn.Esc() < escFuncTagged {
		if fn.Defn.Esc() == escFuncUnknown {
			base.Fatalf("graph inconsistency: %v", fn)
		}
		return true
	}
	return false
}

const (
	escFuncUnknown = 0 + iota
	escFuncPlanned
	escFuncStarted
	escFuncTagged
)

// 将没有回跳的标签标记为不增加e.loopdepth。
type labelState int

const (
	looping labelState = 1 + iota
	nonlooping
)

func (b *batch) paramTag(fn *ir.Func, narg int, f *types.Field) string {
	name := func() string {
		if f.Sym != nil {
			return f.Sym.Name
		}
		return fmt.Sprintf("arg#%d", narg)
	}

	// 仅报告用户代码的诊断；
	// 不适用于围绕它们生成的包装。
	// TODO（mdempsky）：概括一下。
	diagnose := base.Flag.LowerM != 0 && !(fn.Wrapper() || fn.Dupok())

	if len(fn.Body) == 0 {
		// 假设uintptr参数必须在整个调用中保持活动。
		// 这对syscall来说是最重要的。系统调用。
		// 见golang。org/issue/13372。
		// 这实际上与escape分析本身没有太大关系，但我们正在重用注释单个函数
		// 参数的功能，并将这些注释传递给导入代码。
		fn.Pragma |= ir.UintptrKeepAlive

		if f.Type.IsUintptr() {
			if diagnose {
				base.WarnfAt(f.Pos, "assuming %v is unsafe uintptr", name())
			}
			return ""
		}

		if !f.Type.HasPointers() { // 不要为标量添加标签
			return ""
		}

		var esc leaks

		// 外部函数被认为是不安全的，除非
		// 
		if fn.Pragma&ir.Noescape != 0 {
			if diagnose && f.Sym != nil {
				base.WarnfAt(f.Pos, "%v does not escape", name())
			}
		} else {
			if diagnose && f.Sym != nil {
				base.WarnfAt(f.Pos, "leaking param: %v", name())
			}
			esc.AddHeap(0)
		}

		return esc.Encode()
	}

	if fn.Pragma&ir.UintptrEscapes != 0 {
		fn.Pragma |= ir.UintptrKeepAlive

		if f.Type.IsUintptr() {
			if diagnose {
				base.WarnfAt(f.Pos, "marking %v as escaping uintptr", name())
			}
			return ""
		}
		if f.IsDDD() && f.Type.Elem().IsUintptr() {
			// 最后一个参数是。。。uintptr。
			if diagnose {
				base.WarnfAt(f.Pos, "marking %v as escaping ...uintptr", name())
			}
			return ""
		}
	}

	if !f.Type.HasPointers() { // 不要为标量添加标签
		return ""
	}

	// 未命名的参数未使用，因此不能转义。
	if f.Sym == nil || f.Sym.IsBlank() {
		var esc leaks
		return esc.Encode()
	}

	n := f.Nname.(*ir.Name)
	loc := b.oldLoc(n)
	esc := loc.paramEsc
	esc.Optimize()

	if diagnose && !loc.escapes {
		if esc.Empty() {
			base.WarnfAt(f.Pos, "%v does not escape", name())
		}
		if x := esc.Heap(); x >= 0 {
			if x == 0 {
				base.WarnfAt(f.Pos, "leaking param: %v", name())
			} else {
				// TODO（mdempsky）：像下面这样提到level=x？
				base.WarnfAt(f.Pos, "leaking param content: %v", name())
			}
		}
		for i := 0; i < numEscResults; i++ {
			if x := esc.Result(i); x >= 0 {
				res := fn.Type().Results().Field(i).Sym
				base.WarnfAt(f.Pos, "leaking param: %v to result %v level=%d", name(), res, x)
			}
		}
	}

	return esc.Encode()
}
